/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package pratica7;

import java.util.ArrayList;

public class MinHeap<E> {

    public ArrayList<E> heap;

    public MinHeap(ArrayList<E> elements) {
        this.heap = (ArrayList<E>) elements.clone();
        for (int i = ((heap.size() / 2) - 1); i >= 0; i--) {
            this.min_heapify(i);
        }
    }

    public boolean contains(E e) {
        return heap.contains(e);
    }

    public void add_element(E e) {
        int i = heap.size();
        Comparable c = null;
        if (heap.size() > (i - 1) / 2) {
            c = (Comparable) heap.get((i - 1) / 2);
            while (i > 0 && c.compareTo(e) > 1) {
                heap.set(i, heap.get((i - 1) / 2));
                i = (i - 1) / 2;
                c = (Comparable) heap.get((i - 1) / 2);
            }
        }
        heap.add(i, e);
    }

    public E pop() {
        this.min_heapify(0);
        if (heap.size() >= 1) {
            E min = heap.remove(0);
            return min;
        }
        return null;
    }

    private void min_heapify(int i) {
        int l = ((i * 2) + 1);
        int r = ((i * 2) + 2);
        int smallest = i;
        Comparable left, right;
        if (l < heap.size()) {
            left = (Comparable) heap.get(l);
            if (left.compareTo((Comparable) heap.get(i)) < 0)
                smallest = l;
        }
        if (r < heap.size()) {
            right = (Comparable) heap.get(r);
            if (right.compareTo((Comparable) heap.get(smallest)) < 0)
                smallest = r;
        }
        if (smallest != i) {
            E tmp = heap.get(i);
            heap.set(i, heap.get(smallest));
            heap.set(smallest, tmp);
            min_heapify(smallest);
        }
    }

    public ArrayList<E> getHeap() {
        return heap;
    }

    public int size() {
        return heap.size();
    }

}
